package com.test.daily.leetcode.y2022.m05.day0519.v07;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/19 下午 11:14
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }

        // 找到链表的第一个环节点，如果没有，则返回null
        public static Node getLoopNode(Node head) {
            if (head == null || head.next == null || head.next.next != null) {
                return null;
            }
            Node slow = head.next;
            Node fast = head.next.next;
            while (fast != slow) {
                if (fast.next == null || fast.next.next == null) {
                    return null;
                }
                fast = fast.next.next;
                slow = slow.next;
            }
            fast = head;
            while (fast != slow) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

        // 1. 找到较长的链表
        // 2. 较长的链表来到差距值的位置
        // 3. 两个链表齐头并进直到相同
        public static Node noLoop(Node head1, Node head2) {
            if (head1 == null || head2 == null) {
                return null;
            }
            int n = 0;
            Node cur1 = head1;
            Node cur2 = head2;
            while(cur1 != null){
                n++;
                cur1 = cur1.next;
            }
            while(cur2 != null){
                cur2 = cur2.next;
                n--;
            }
            cur1 = n > 0 ? head1: head2;
            cur2 = cur1 == head1 ? head2: head1;
            n = Math.abs(n);
            while(n != 0){
                cur1 = cur1.next;
            }
            while (cur1 != cur2){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }

        // 两个有环链表，返回第一个相交的节点，如果不相交，则返回为空
        public static Node bothLoop(Node head1, Node head2, Node n1, Node n2){

            return null;
        }

    }
}
